package org.liaohailong.victor;

import java.util.LinkedList;

/**
 * Author: liaohailong
 * Date: 2022/2/14
 * Time: 16:42
 * Description:
 **/
public class OtherStudy {

    // 两整数之和
    public int getSum(int a, int b) {
        if (a == 0) return b;
        return getSum((a & b) << 1, a ^ b);
    }

    // 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        LinkedList<Integer> values = new LinkedList<>();
        for (String token : tokens) {
            if (isOp(token)) {
                int val2 = values.pollLast();
                int val1 = values.pollLast();
                int val = doOp(val1, val2, token);
                values.addLast(val);
            } else {
                values.addLast(Integer.parseInt(token));
            }
        }
        return values.poll();
    }

    private boolean isOp(String s) {
        switch (s) {
            case "+":
            case "-":
            case "*":
            case "/":
                return true;
        }
        return false;
    }

    private int doOp(int val1, int val2, String op) {
        switch (op) {
            case "+":
                return val1 + val2;
            case "-":
                return val1 - val2;
            case "*":
                return val1 * val2;
            case "/":
                return val1 / val2;
        }
        return 0;
    }


    // 多数元素
    public int majorityElement(int[] nums) {
        // 对拼抵消 时间：On 空间：O1
        int count = 1;
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == res) {
                count++;
            } else if (count == 0) {
                res = nums[i];
                count = 1;
            } else {
                count--;
            }
        }

        return res;
    }


    // 任务调度器
    public int leastInterval(char[] tasks, int n) {
        int size = tasks.length;
        int[] hash = new int[26];
        int maxSize = 0;
        //求出出现的最高次数
        for (char t : tasks) {
            hash[t - 'A']++;
            maxSize = Math.max(maxSize, hash[t - 'A']);
        }
        int maxCount = 0;
        //求出现最高次的频率
        for (int i = 0; i < 26; i++) {
            if (hash[i] == maxSize)
                maxCount++;
        }
        int res = (maxSize - 1) * (n + 1) + maxCount;
        //一旦出现res小于数组长度，答案就为数组长度
        return Math.max(res, size);

        // 推导公式逻辑：
        // 先找出出现频率最大的数字
        // 例如：[A,A,A,B,B,C,C,] 就是A出现了三次
        // 最快的排序 A,B,C,A,B,C,A /ABC/ABC/A
        // 另外一种情况：[A,A,A,B,B,B,C,C] /ABC/ABC/AB
        // 首先最后一部分不看，前面就有(最多频次 - 1)次的字母任务组合，其余数字往中间插入
        // 再找出相同的最大任务数量，这里有3个A，3个B，所以做完两组/ABC/ABC之后，还有两个单元任务
        // 推导公式：
        // (maxSec - 1) * n + (maxSec - 1) + maxCount
        // 简化为：
        // (maxSec - 1) * (n + 1) + maxCount
    }
}
